The present application relates to locating a unique or specific item in a Peer-to-Peer (P2P) network, and more particularly to locating a person in the P2P network.
Many exciting applications, such as Voice over IP (VoIP) and Instant Messaging (IM), would benefit from the support of efficient person search. Nowadays, the search mechanisms for these applications still operate in a rather centralized manner. Users are required to register with a central server when they log into the system and query it for the addresses of their target search people. This is not scalable and the server introduces a single point of failure.
In person-searching applications (as in VoIP and IM), a person usually has a hot list which contains the people he/she often calls, such as colleagues, family members and friends. It has long been observed that human communication, and hence the hot list, exhibits the following characteristics:                Strong access skewness: Hot list is often short (of size around not more than ten), which means that contacts often skewed towards only a few people. Some people also are popular and have a relatively dense social connection. They are not only often called, but also good candidates to be contacted when searching for an unknown person.        User-dependent: The calls and hot lists are very user-dependent or user-specific, where a person popular in one domain may not be so in another.        Dense social network: Social network has high locality and is closely knit together. This is the so-called “small world” effect in which the person called is likely known by caller's direct or non-distant friends. Furthermore, users in the same domain (say within the same company or institute) or community (say alumni of a university) often communicate with each other.        
It is clear that in order to locate a person efficiently, the search mechanism should take advantage of the above communication patterns. Hence the person searching differs from the traditional file searching in two major ways:                Item uniqueness: While multiple copies of files or resources exist in a file sharing system, the target item being located here is unique. Consequently, schemes taking advantage of the popularity of items (such as random walk and flooding) would not be efficient.        Access pattern: Contrasting with file searching where the file popularity is generally assumed to be the same for all users, the access pattern in person searching is very user-dependent and domain-specific. This fundamentally changes the underlying system assumption. If one naively applies file-search mechanisms to person-searching, the search therefore would not be effective.        
Generally, P2P overlay networks can be categorized into unstructured and structured. In an unstructured overlay (such as Gnutella), peers are organized in a random graph and flooding or random walks is used to locate items. Clearly, it is very resource consuming to search for rare items on a large network. A negative answer to a search may mean that either the item does not exist or it is not found within a certain search scope. A structured overlay such as Pastry overcomes the search inefficiency for rare items. It assigns keys to items using a hash table and organizes the participating peers into a graph based on their IDs (the so-called nodeID). The graph is structured to facilitate the search for an item based on its key, by routing the message to a responsible peer who has nodeID numerically closest to the key.